/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 combat_path_finder.cpp

	$Header: /heroes4/combat_path_finder.cpp $

	$NoKeywords: $

 ************************************************************************/
// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "combat_path_finder.h"

#include "attackable_obstacle.h"
#include "combat_creature.h"
#include "combat_footprint.h"
#include "battlefield.h"
#include "direction.h"
#include "enum_operations.h"
#include "hero.h"
#include "map_rect.h"
#include "obstacle_type.h"
#include "skill.h"
#include "spell.h"
#include "stationary_combat_object.h"
#include "terrain.h"

int const k_tower_entry_cost = 400;
int const k_tower_exit_cost = 400;

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
t_combat_path_finder::t_combat_path_finder( t_combat_creature const& army, 
										    bool ignore_unattackable )
					: t_combat_path_finder_base( army.get_battlefield().get_size() )
{
	m_army = &army;
	m_ignore_unattackable = ignore_unattackable;
	m_initialized = false;
	if (m_army->has_ability( k_ability_teleport ))
		m_teleporting = true;
	else
		m_teleporting = false;
}

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
bool t_combat_path_finder::contains_water( t_map_point_2d const& point ) const
{
	if (m_army->is_active( k_spell_terrain_walk ))
		return false;

	t_combat_footprint const& footprint = m_army->get_footprint();
	int                       footprint_size = footprint.get_size();
	t_map_point_2d            offset;
	t_map_point_2d            new_point;
	int const*				  ptr = footprint.get();
	t_battlefield_cell const* cell;
	t_battlefield const&      battlefield = m_army->get_battlefield();

	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = point + offset;
			cell = &battlefield.get_cell( new_point );
			if (cell->get_creature() == m_army)
				continue;
			if (cell->has_gate())
				continue;
			if (cell->get_terrain_type() == k_terrain_water_river)
				return true;
		}
	}
	return false;
}


// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
bool t_combat_path_finder::contains_quicksand( t_map_point_2d const& point ) const
{
	if (m_army->is_active( k_spell_terrain_walk ))
		return false;

	t_combat_footprint const& footprint = m_army->get_footprint();
	int                       footprint_size = footprint.get_size();
	t_map_point_2d            offset;
	t_map_point_2d            new_point;
	int const*				  ptr = footprint.get();
	t_battlefield const&      battlefield = m_army->get_battlefield();
	t_battlefield_cell const* cell;

	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = point + offset;
			cell = &battlefield.get_cell( new_point );
			if (cell->get_creature() == m_army || cell->has_gate())
				continue;
			if (cell->is_quicksand())
				return true;
		}
	}
	return false;
}


// ---------------------------------------------------------------
// class to find paths for combat map
// mark areas next to arrow tower as starting positions
// ---------------------------------------------------------------
void t_combat_path_finder::initialize_tower( t_map_rect_2d const& rect, 
											 t_map_point_2d const& step )
{
	t_map_point_2d		point;
	t_combat_path_data*	path_point;
	t_map_point_2d		last_point = m_army->get_cell_position();

	t_combat_path_data& initial = m_data.get( last_point );

	initial.move_cost = 0;
	initial.last_point.row = -1;
	initial.last_point.column = -1;
	initial.visited = true;
	initial.reachable = true;
	initial.flight_cost = 0;
	initial.nearest_point = last_point;
	initial.blocked = false;
	initial.off_map = false;
	initial.forbidden = false;
	initial.is_tower = true;
	initial.has_wall = false;

	for (point.row = rect.top_left.row; point.row < rect.bottom_right.row; 
	     point.row += step.row )
	{
		for (point.column = rect.top_left.column; point.column < rect.bottom_right.column;
		     point.column += step.column )
		{
			if (!m_data.is_valid( point ))
				continue;
			path_point = &m_data.get( point );
			if (path_point->off_map)
				continue;
			if (path_point->blocked)
				continue;

			t_combat_path_point start( point );

			start.off_map = false;
			start.forbidden = false;
			start.entry_cost = 100;
			start.move_cost = k_tower_exit_cost;
			start.visited = true;
			start.reachable = true;
			start.flight_cost = 0;
			start.nearest_point = start;
			start.blocked = false;
			start.is_tower = false;
			start.has_wall = false;
			start.attackable = false;
			start.last_point = last_point;
			start.direction = get_direction( last_point, point );
			m_open_points.push( start );
			// set initial point
			m_data.get( start ) = start;
		}
	}
}

// ---------------------------------------------------------------
// class to find paths for combat map
// mark positions next to an arrow tower as starting positions
// ---------------------------------------------------------------
void t_combat_path_finder::tower_initialization()
{
	// mark all points next to tower as startable
	t_map_point_2d				tower_position;
	t_stationary_combat_object* tower;
	t_battlefield&				battlefield = m_army->get_battlefield();
	int							tower_footprint_size;
	int							footprint_size = m_army->get_footprint_size();
	t_map_rect_2d				rect;
	t_map_point_2d				step;

	m_open_points.clear();
	tower = m_army->get_tower();
	assert( tower != 0 );
	assert( tower->get_obstacle_type() == k_obstacle_castle_tower );
	tower_position = tower->get_cell_position();
	tower_footprint_size = tower->get_footprint_size();

	rect.top_left.column = tower_position.column - footprint_size;
	rect.bottom_right.column = tower_position.column + tower_footprint_size + 1;
	rect.top_left.row = tower_position.row;
	rect.bottom_right.row = tower_position.row + tower_footprint_size - footprint_size + 1;
	step.row = 1;
	step.column = tower_footprint_size + footprint_size;
	initialize_tower( rect, step );
	rect.top_left.column = tower_position.column;
	rect.bottom_right.column = tower_position.column + tower_footprint_size - footprint_size + 1;
	step.column = 1;
	rect.top_left.row = tower_position.row - footprint_size;
	rect.bottom_right.row = tower_position.row + tower_footprint_size + 1;
	step.row = tower_footprint_size + footprint_size;
	initialize_tower( rect, step );
}

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
static void mark_path_map( t_combat_path_map& map, t_combat_creature const* army,
						   bool ignore_unattackable )
{
	t_battlefield const&			battlefield = army->get_battlefield();
	t_combat_object_const_iterator  index = battlefield.objects_begin();
	t_combat_object_const_iterator  end = battlefield.objects_end();
	t_abstract_combat_object const* object;
	t_combat_path_blockage			blockage;
	t_combat_path_blockage			tower_value;
	t_combat_path_blockage			wall_value;
	t_combat_path_blockage			gate_value;

	bool can_cross_gate = ignore_unattackable || 
						  battlefield.gate_is_open() ||
						  (army->controlled_by( true ) && !battlefield.gate_is_blocked());

	blockage.blocked = true;
	blockage.in_tower = false;
	blockage.has_wall = false;
	tower_value.blocked = false;
	tower_value.in_tower = true;
	tower_value.has_wall = false;
	wall_value.blocked = true;
	wall_value.in_tower = false;
	wall_value.has_wall = true;
	gate_value.blocked = !can_cross_gate;
	gate_value.in_tower = false;
	gate_value.has_wall = !battlefield.gate_is_open();


	for (; index != end; index++)
	{
		object = index->get();
		if (!object->blocks_movement())
			continue;
		if (object->is_permanent())
			continue;
		if (object == army)
			continue;


		const t_stationary_combat_object const *stationary_object = dynamic_cast<const t_stationary_combat_object*>(object);
		if (stationary_object) 
		{
			switch (stationary_object->get_obstacle_type()) {
			  case k_obstacle_castle_wall:
				map.mark_obstacle( *object, wall_value );
				continue;

			  case k_obstacle_castle_gate:
				map.mark_obstacle( *object, gate_value );
				continue;

			  case k_obstacle_castle_tower:
				{
					// check if it is occupied
					t_map_point_2d						position;
					t_map_point_2d						center;
					int									footprint_size;
					
					position = stationary_object->get_cell_position();
					footprint_size = stationary_object->get_footprint_size() >> 1;
					center.row = position.row + footprint_size;
					center.column = position.column + footprint_size;
					
					t_combat_creature *creature = battlefield.get_creature( center );
					if ( creature == 0 || 
						 ( ignore_unattackable && 
						  ( !creature->is_hostile(*army)     || 
						    army->check_cowardice(*creature) || 
							creature->is_active(k_spell_sanctuary) ) ) )
					{
						// mark all squares in the tower as passable and in a tower
						map.mark_obstacle( *object, tower_value );
					}
				}
				continue;

			  default:
				;// Fall through to code below
			}
		}


		if (ignore_unattackable)
		{
			// Ignore friendlies which cannot be attacked
			// Ignore summoned rocks and castle gates which can be attacked
			const t_combat_creature *creature = dynamic_cast<const t_combat_creature *>(object);
			
			if (creature)
			{
				if (!creature->is_hostile(*army))
					continue;
				
				if (army->check_cowardice(*creature))
					continue;
				
				if (creature->is_active(k_spell_sanctuary))
					continue;
			}
			else
			{
				// Is it a non-creature attackable object?
				if (object->can_be_attacked())
					continue;
			}
		}
		map.mark_obstacle( *object, blockage );
	}
}


// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
void t_combat_path_finder::initialize()
{
	if (m_initialized || m_army == 0)
		return;

	m_initialized = true;

	// mark which areas are blocked for travel
	t_battlefield&			battlefield = m_army->get_battlefield();
	t_ai_combat_data_cache& data_cache = battlefield.get_data_cache();
	int						footprint_size = m_army->get_footprint_size();

	m_data = data_cache.get_obstacle_map( footprint_size );

	mark_path_map( m_data, m_army, m_ignore_unattackable );
	if (m_army->is_in_tower())
		tower_initialization();
	else
		push_first_point( m_army->get_cell_position() );

	// check quicksand
	t_map_point_2d				point;
	int							row_end;
	t_combat_path_data*			ptr;
	bool						mark_gate = false;
	t_combat_terrain_map		terrain_map = data_cache.get_terrain_map( footprint_size );
	t_terrain_bit_cost_array	costs;
	t_uint32					bits;
	int							i;

	// if castle gate could open as part of the move, temporarily mark
	// the gate as open so we can move freely in the gate area.
	if ( !m_teleporting && !m_army->is_flying() )
	{
		costs.compute( *m_army );

		if ( battlefield.has_gate() && !battlefield.gate_is_open() && 
			 m_army->controlled_by( true ) &&
			 m_army->get_cell_position().row < battlefield.get_castle_row() )
		{
			mark_gate = true;
			battlefield.mark_gate( true );
			terrain_map.refresh( battlefield.get_gate_rect(), m_army );
		}
	}

	terrain_map.refresh( m_army );

	t_uint32 all_bits = 0;

	i = costs.size();
	while (i--)
		all_bits |= costs[i].bit;
	
	point.row = m_data.get_size();
	while (point.row--)
	{
		point.column = m_data.get_row_start( point.row );
		row_end = m_data.get_row_end( point.row );
		ptr = &m_data.get( point );
		while (point.column < row_end)
		{
			if (ptr->is_tower)
				ptr->entry_cost = k_tower_entry_cost;
			else 
			{
				ptr->entry_cost = 100;
				if (!ptr->blocked)
				{
					bits = terrain_map.get( point );
					if (bits & all_bits)
					{
						i = costs.size();
						while (i--)
						{
							if (bits & costs[i].bit)
							{
								ptr->entry_cost = costs[i].cost;
								break;
							}
						}
					}
				}
			}
			ptr++;
			point.column++;
		}
	}

	// restore the state of the castle gate.
	if (mark_gate)
		battlefield.mark_gate( false );
}

// ---------------------------------------------------------------
// class to find paths for combat map
// ---------------------------------------------------------------
void t_combat_path_finder::generate_paths()
{
	if (m_initialized)
		return;

	initialize();

	t_combat_path_point			point;
	t_direction					direction;
	int							flight_cost;
	int							move_cost;
	int							attack_distance_limit = m_army->get_attack_range() * 2;
	bool						impeded_directions[k_direction_count];
	int							move = m_army->get_combat_movement();
	int							impeded_move_cost = move >> 2;
	bool						flying = m_army->is_flying();
	int							wall_flight_cost;
	t_combat_path_data const*	last_cell;
	t_battlefield&				battlefield = m_army->get_battlefield();

	if (m_open_points.empty())
		return;

	if (m_army->is_active( k_spell_binding ))
		m_open_points.clear();

	memset( impeded_directions, 0, sizeof( impeded_directions ));
	// walls are 2 wide, so moving inward costs just enough that crossing 2 walls
	// allows you to just touch down on the other side.
	if (m_teleporting)
		wall_flight_cost = 100;
	else
	{
		wall_flight_cost = (move - 200) / (m_army->get_footprint_size() + 1);
		if (wall_flight_cost < 100)
			wall_flight_cost = 100;
	}
	while (!m_open_points.empty())
	{
		point = m_open_points.top();
		m_open_points.pop();
		if (!m_teleporting)
			battlefield.get_impeded_angles( *m_army, point, impeded_directions );
		last_cell = &m_data.get( point );
		for (direction = t_direction(0); direction < k_direction_count; enum_incr( direction ))
		{
			t_map_point_2d new_map_point( point );
			
			new_map_point += get_direction_offset( direction );
			if (!m_data.is_valid( new_map_point ))
				continue;

			t_combat_path_data& cell = m_data.get( new_map_point );

			if (cell.off_map)
				continue;
			if (!last_cell->visited)
			{
				// last cell wasn't visited, we're just marking attack distance.
				// if new cell is visited, no point in continuing.
				if (cell.visited)
					continue;
				assert( last_cell->attackable );

				// check if new attack distance exceeds old, or we've exceeded the limit
				int new_distance = last_cell->attack_distance + 2 + (direction & 1);

				if (new_distance > attack_distance_limit)
					continue;
				if ( cell.attackable && cell.attack_distance <= new_distance )
					continue;

				// save the new point
				cell.move_cost = last_cell->move_cost + 500;
				cell.last_point	= point;
				cell.direction	= direction;
				cell.attackable = true;
				cell.attack_distance = new_distance;
				m_open_points.push( t_combat_path_point( new_map_point, cell ) );
				continue;
			}
			if (cell.visited && cell.move_cost <= last_cell->move_cost)
				continue;

			if (cell.blocked && !flying && !m_teleporting)
			{
				// check if new attack distance exceeds old, or we've exceeded the limit
				int new_distance = 2 + (direction & 1);

				if (last_cell->move_cost > move)
					continue;
				if ( cell.attackable && cell.attack_distance <= new_distance )
					continue;

				// save the new point as an attackable but unreachable point
				cell.move_cost = last_cell->move_cost + 500;
				cell.last_point	= point;
				cell.direction	= direction;
				cell.attackable = true;
				cell.attack_distance = 2 + (direction & 1);
				m_open_points.push( t_combat_path_point( new_map_point, cell ) );
				continue;
			}

			if (last_cell->is_tower)
			{
				
				if (cell.is_tower)
				{	// towers use a zero internal cost, since there's really only 1 interior point.
					// unless the tower is blocked and we're flying over it.
					if (cell.blocked)
						move_cost = 100;
					else
						move_cost = 0;
				}
				else
				{	// if this is our first move, pay tower exit cost.  Otherwise pay
					// full move, since we should not both enter and exit the tower.
					if (last_cell->move_cost == 0)
						move_cost = k_tower_exit_cost;
					else
						move_cost = move;
				}
			}
			else
			{	// compute normal movement cost.
				// flying over walls requires extra movement if we're flying into the castle.
				if (!flying && !m_teleporting)
					move_cost = cell.entry_cost;
				else if (cell.has_wall 
						 && (direction <= k_direction_east || direction == k_direction_north) )
					move_cost = wall_flight_cost;
				else
					move_cost = 100;
			}
			// include any ZOC effects
			if (impeded_directions[direction])
				move_cost += impeded_move_cost;
			// add 50% for diagonal moves.
			if (direction & 1)
				move_cost += move_cost >> 1;
			if (last_cell->blocked || cell.blocked)
			{
				flight_cost = last_cell->flight_cost + move_cost;
				if (flight_cost > move)
					continue;
			}
			else
				flight_cost = 0;
			move_cost += last_cell->move_cost;
			if (cell.visited && move_cost >= cell.move_cost)
				continue;

			cell.attack_distance	= 2 + (direction & 1);
			cell.attackable			= last_cell->move_cost <= move;
			cell.move_cost			= move_cost;
			cell.flight_cost		= flight_cost;
			cell.visited			= true;
			cell.reachable			= !cell.blocked;
			cell.nearest_point		= new_map_point;
			cell.last_point			= point;
			cell.direction			= direction;
			m_open_points.push( t_combat_path_point( new_map_point, cell ) );
		}
	}
	mark_reachable_points( m_army->get_footprint() );
}

